/**
Copyright (c) 2013, Andy Fox (andy.fox at qq.com)
All rights reserved.

Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this
  list of conditions and the following disclaimer in the documentation and/or
  other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#include "bsd_hash.h"

typedef struct bsd_hash_entry_t {
    struct bsd_hash_entry_t *next;
    u32                      hash;
    const void              *key;
    u32                      klen;
    const void              *val;
} bsd_hash_entry_t;

struct bsd_hash_index_t {
    bsd_hash_t         *ht;
    bsd_hash_entry_t   *this, *next;
    unsigned int        index;
};

struct bsd_hash_t {
    bsd_hash_entry_t   **array;
    bsd_hash_index_t     iterator;
    u32                  count, max, seed;
    u32                  flag;
    bsd_hash_fn          hash_func;
    bsd_hash_entry_t    *free;
};

#define BSD_HASH_MAX        15 /* 2^n - 1 */

#define BSD_HASH_FLAG_MAKE  0x10
#define BSD_HASH_FLAG_COPY  0x20

static bsd_hash_entry_t **alloc_array(bsd_hash_t *ht, u32 max)
{
    bsd_hash_entry_t **hep = bsd_malloc(sizeof(*ht->array) * (max + 1));
    if (hep) {
        memset(hep, 0, sizeof(*ht->array) * (max + 1));
    }
   return hep;
}

static void expand_array(bsd_hash_t *ht)
{
    bsd_hash_index_t *hi;
    bsd_hash_entry_t **new_array;
    u32 new_max;

    new_max = ht->max * 2 + 1;
    new_array = alloc_array(ht, new_max);
    if (!new_array) {
        return ;
    }

    for (hi = bsd_hash_first(ht); hi; hi = bsd_hash_next(hi)) {
        u32 i = hi->this->hash & new_max;
        hi->this->next = new_array[i];
        new_array[i] = hi->this;
    }
    ht->array = new_array;
    ht->max = new_max;
    BSD_LOG_OUT("expand_array ok\n");
}

static u32 hashfunc_default(const char *char_key, u32 *klen, u32 hash)
{
    const u8 *key = (const u8 *)char_key;
    const u8 *p;
    u32 i;

    if (*klen == BSD_HASH_KEY_STRING) {
        for (p = key; *p; p++) {
            hash = hash * 33 + *p;
        }
        *klen = p - key;
    } else {
        for (p = key, i = *klen; i; i--, p++) {
            hash = hash * 33 + *p;
        }
    }

    return hash;
}

static bsd_hash_entry_t **find_entry(bsd_hash_t *ht, const void *key,
                            u32 klen,  const void *val)
{
    bsd_hash_entry_t **hep, *he;
    u32 hash;

    hash = ht->hash_func(key, &klen);

    /* scan linked list */
    for (hep = &ht->array[hash & ht->max], he = *hep;
         he; hep = &he->next, he = *hep) {
        if (he->hash == hash
            && he->klen == klen
            && memcmp(he->key, key, klen) == 0)
            break;
    }
    if (he || !val)
        return hep;

    /* add a new entry for non-NULL values */
    if ((he = ht->free) != BSD_NULL) {
        ht->free = he->next;
    } else {
        he = bsd_malloc(sizeof(*he));
        if (!he) {
            return BSD_NULL;
        }
        BSD_LOG_OUT("malloc %p\n", he);
    }
    he->next = BSD_NULL;
    he->hash = hash;
    he->key  = key;
    he->klen = klen;
    he->val  = val;
    *hep = he;
    ht->count++;
    return hep;
}

unsigned int bsd_hashfunc_default(const char *char_key, u32 *klen)
{
    return hashfunc_default(char_key, klen, 0);
}

bsd_hash_t *bsd_hash_make(bsd_hash_fn hash_func)
{
    bsd_hash_t *ht;

    ht = bsd_malloc(sizeof(bsd_hash_t));
    if (!ht) {
        BSD_LOG_OUT("bsd_malloc error at %d\n", __LINE__);
        return BSD_NULL;
    }

    ht->max = BSD_HASH_MAX;
    ht->array = alloc_array(ht, ht->max);
    if (!ht->array) {
        BSD_LOG_OUT("bsd_malloc error at %d\n", __LINE__);
        return BSD_NULL;
    }

    ht->free = BSD_NULL;
    ht->count = 0;
    ht->seed = 0;
    ht->flag = BSD_HASH_FLAG_MAKE;
    if (hash_func) {
        ht->hash_func = hash_func;
    } else {
        ht->hash_func = bsd_hashfunc_default;
    }
    return ht;
}

void bsd_hash_free(bsd_hash_t *ht)
{
    if (ht) {
        if (ht->flag & BSD_HASH_FLAG_COPY) {
            bsd_free(ht);
            return;
        }

        bsd_hash_clear(ht);
        if (ht->array) {
            bsd_free(ht->array);
        }

        while (ht->free) {
            bsd_hash_entry_t *he = ht->free;
            ht->free = he->next;
            BSD_LOG_OUT("free %p\n", he);
            bsd_free(he);
        }
        bsd_free(ht);
    }
}

bsd_hash_index_t *bsd_hash_next(bsd_hash_index_t *hi)
{
    hi->this = hi->next;
    while (!hi->this) {
        if (hi->index > hi->ht->max)
            return BSD_NULL;

        hi->this = hi->ht->array[hi->index++];
    }
    hi->next = hi->this->next;
    return hi;
}

bsd_hash_index_t *bsd_hash_first(bsd_hash_t *ht)
{
    bsd_hash_index_t *hi = &ht->iterator;

    hi->ht = ht;
    hi->index = 0;
    hi->this = BSD_NULL;
    hi->next = BSD_NULL;
    return bsd_hash_next(hi);
}

void bsd_hash_this(bsd_hash_index_t *hi, const void **key, u32 *klen, void **val)
{
    if (key)  *key  = hi->this->key;
    if (klen) *klen = hi->this->klen;
    if (val)  *val  = (void *)hi->this->val;
}

bsd_hash_t * bsd_hash_copy(const bsd_hash_t *orig)
{
    bsd_hash_t *ht;
    bsd_hash_entry_t *new_vals;
    u32 i, j;

    ht = bsd_malloc(sizeof(bsd_hash_t) +
                    sizeof(*ht->array) * (orig->max + 1) +
                    sizeof(bsd_hash_entry_t) * orig->count);
    if (!ht) {
        BSD_LOG_OUT("bsd_malloc error at %d\n", __LINE__);
        return BSD_NULL;
    }

    ht->count = orig->count;
    ht->max = orig->max;
    ht->seed = orig->seed;
    ht->flag = BSD_HASH_FLAG_COPY;
    ht->hash_func = orig->hash_func;
    ht->free = BSD_NULL;

    ht->array = (bsd_hash_entry_t **)((char *)ht + sizeof(bsd_hash_t));
    new_vals = (bsd_hash_entry_t *)((char *)(ht) + sizeof(bsd_hash_t) +
                                    sizeof(*ht->array) * (orig->max + 1));
    j = 0;
    for (i = 0; i <= ht->max; i++) {
        bsd_hash_entry_t **new_entry = &(ht->array[i]);
        bsd_hash_entry_t *orig_entry = orig->array[i];
        while (orig_entry) {
            *new_entry = &new_vals[j++];
            (*new_entry)->hash = orig_entry->hash;
            (*new_entry)->key = orig_entry->key;
            (*new_entry)->klen = orig_entry->klen;
            (*new_entry)->val = orig_entry->val;
            new_entry = &((*new_entry)->next);
            orig_entry = orig_entry->next;
        }
        *new_entry = BSD_NULL;
    }
    return ht;
}

void *bsd_hash_get(bsd_hash_t *ht, const void *key, u32 klen)
{
    bsd_hash_entry_t *he;
    he = *find_entry(ht, key, klen, BSD_NULL);
    if (he)
        return (void *)he->val;
    else
        return BSD_NULL;
}

void bsd_hash_set(bsd_hash_t *ht, const void *key, u32 klen, const void *val)
{
    bsd_hash_entry_t **hep;
    hep = find_entry(ht, key, klen, val);
    if (*hep) {
        if (!val) {
            /* delete entry */
            bsd_hash_entry_t *old = *hep;
            *hep = (*hep)->next;
            old->next = ht->free;
            ht->free = old;
            --ht->count;
        }
        else {
            /* replace entry */
            (*hep)->val = val;
            /* check that the collision rate isn't too high */
            if (ht->count > ht->max) {
                expand_array(ht);
            }
        }
    }
    /* else key not present and val==BSD_NULL */
}

u32 bsd_hash_count(bsd_hash_t *ht)
{
    return ht->count;
}

void bsd_hash_clear(bsd_hash_t *ht)
{
    bsd_hash_index_t *hi;

    for (hi = bsd_hash_first(ht); hi; hi = bsd_hash_next(hi))
        bsd_hash_set(ht, hi->this->key, hi->this->klen, BSD_NULL);
}

int bsd_hash_do(bsd_hash_callback_fn comp, void *rec, const bsd_hash_t *ht)
{
    bsd_hash_index_t  hix;
    bsd_hash_index_t *hi;
    int rv, dorv  = 1;

    hix.ht    = (bsd_hash_t *)ht;
    hix.index = 0;
    hix.this  = BSD_NULL;
    hix.next  = BSD_NULL;

    if ((hi = bsd_hash_next(&hix))) {
        /* Scan the entire table */
        do {
            rv = comp(rec, hi->this->key, hi->this->klen, hi->this->val);
        } while (rv && (hi = bsd_hash_next(hi)));

        if (rv == 0) {
            dorv = 0;
        }
    }
    return dorv;
}

#if BSD_TEST_FLAG
#include <stdio.h>
#include <assert.h>
#include <malloc.h>

static u32 hash_custom( const char *key, u32 *klen)
{
    u32 hash = 0;
    u32 len = *klen;
    while( len ) {
        (len) --;
        hash = hash * 331 + key[ len ];
    }
    return hash;
}

int hash_cb_fn(void *rec, const void *key, u32 klen, const void *value)
{
    static int id = 0;
    BSD_LOG_OUT("[%02d] key: %s, klen: %d, value: %s\n", id++, key, klen, value);
    return 1;
}


void bsd_hash_test()
{
    int i, *e, ee;
    char *result = BSD_NULL;
    bsd_hash_t *test_ht = BSD_NULL;
    bsd_hash_t *test_ht2 = BSD_NULL;

    test_ht = bsd_hash_make(BSD_NULL);
    BSD_ASSERT(test_ht != BSD_NULL);
    BSD_LOG_OUT("bsd_hash_make ok\n");

    bsd_hash_set(test_ht, "key", BSD_HASH_KEY_STRING, "value");
    result = bsd_hash_get(test_ht, "key", BSD_HASH_KEY_STRING);
    BSD_ASSERT(strcmp(result, "value") == 0);
    BSD_LOG_OUT("bsd_hash_set ok\n");

    bsd_hash_set(test_ht, "key", BSD_HASH_KEY_STRING, "new");
    result = bsd_hash_get(test_ht, "key", BSD_HASH_KEY_STRING);
    BSD_ASSERT(strcmp(result, "new") == 0);
    BSD_LOG_OUT("bsd_hash_get ok\n");

    bsd_hash_set(test_ht, "same1", BSD_HASH_KEY_STRING, "same");
    result = bsd_hash_get(test_ht, "same1", BSD_HASH_KEY_STRING);
    BSD_ASSERT(strcmp(result, "same") == 0);
    BSD_LOG_OUT("same1 ok\n");

    bsd_hash_set(test_ht, "same2", BSD_HASH_KEY_STRING, "same");
    result = bsd_hash_get(test_ht, "same2", BSD_HASH_KEY_STRING);
    BSD_ASSERT(strcmp(result, "same") == 0);
    BSD_LOG_OUT("same2 ok\n");

    bsd_hash_free(test_ht);
    test_ht = bsd_hash_make(hash_custom);
    BSD_ASSERT(test_ht != BSD_NULL);
    BSD_LOG_OUT("hash_custom ok\n");

    bsd_hash_set(test_ht, "same1", 5, "same");
    result = bsd_hash_get(test_ht, "same1", 5);
    BSD_ASSERT(strcmp(result, "same") == 0);
    BSD_LOG_OUT("same1 ok\n");

    bsd_hash_set(test_ht, "same2", 5, "same");
    result = bsd_hash_get(test_ht, "same2", 5);
    BSD_ASSERT(strcmp(result, "same") == 0);
    BSD_LOG_OUT("same2 ok\n");

    bsd_hash_free(test_ht);
    BSD_LOG_OUT("bsd_hash_free ok\n");

    test_ht = bsd_hash_make(BSD_NULL);
    BSD_ASSERT(test_ht != BSD_NULL);
    BSD_LOG_OUT("bsd_hash_make ok\n");

    bsd_hash_set(test_ht, "key with space", BSD_HASH_KEY_STRING, "value");
    result = bsd_hash_get(test_ht, "key with space", BSD_HASH_KEY_STRING);
    BSD_ASSERT(strcmp(result, "value") == 0);
    BSD_LOG_OUT("key with space ok\n");

    for (i = 1; i <= 31; i++) {
        e = bsd_malloc(sizeof(int));
        *e = i+'0';
        bsd_hash_set(test_ht, e, sizeof(*e), e);
    }

    BSD_LOG_OUT("bsd_hash_do 1\n");
    bsd_hash_do(hash_cb_fn, BSD_NULL, test_ht);

    for (i = 1; i <= 16; i++) {
        ee = i+'0';
        bsd_hash_set(test_ht, &ee, sizeof(ee), BSD_NULL);
    }
    BSD_LOG_OUT("bsd_hash_count %d\n", bsd_hash_count(test_ht));


    test_ht2 = bsd_hash_copy(test_ht);
    BSD_LOG_OUT("bsd_hash_do 2\n");
    bsd_hash_do(hash_cb_fn, BSD_NULL, test_ht2);

    bsd_hash_free(test_ht);
    test_ht = test_ht2;

    BSD_LOG_OUT("bsd_hash_count %d\n", bsd_hash_count(test_ht));
    bsd_hash_clear(test_ht);
    BSD_LOG_OUT("bsd_hash_clear ok\n");
    BSD_LOG_OUT("bsd_hash_count %d\n", bsd_hash_count(test_ht));
    bsd_hash_free(test_ht);


}
#endif /* BSD_TEST_FLAG */
